//! @file   lc_basic_string.cpp
//! @brief  
//! @author Sayan Chaliha
//! @date   September, 2011
//!
//! 
#include <lc_forward_decl.h>
#include <lc_basic_string.h>
#include <lc_system.h>
#include <lc_exception.h>
#include <lc_scoped_pointer.h>

namespace cyan {
  template <typename C, typename T>
  const typename BasicString<C, T>::SizeType
  BasicString<C, T>::Rep::maximumSize = (((npos - sizeof (RepBase)) /
      sizeof (ValueType)) - 1) / 4;

  template <typename C, typename T>
  const typename BasicString<C, T>::ValueType
  BasicString<C, T>::Rep::terminal = ValueType();

  template <typename C, typename T>
  const typename BasicString<C, T>::SizeType
  BasicString<C, T>::npos;

  template <typename C, typename T>
  typename BasicString<C, T>::SizeType
  BasicString<C, T>::Rep::emptyRepStorage[(sizeof (RepBase) +
      sizeof (ValueType) + sizeof (SizeType) - 1) / sizeof (SizeType)];

  template <typename C, typename T>
  typename BasicString<C, T>::Rep&
  BasicString<C, T>::Rep::emptyRep() {
    void* p = reinterpret_cast<void*>(&Rep::emptyRepStorage);
    return *reinterpret_cast<Rep*>(p);
  }

  template <typename C, typename T>
  Bool
  BasicString<C, T>::Rep::isLeaked() const {
    return this->referenceCount < 0;
  }

  template <typename C, typename T>
  Bool
  BasicString<C, T>::Rep::isShared() const {
    return this->referenceCount > 0;
  }

  template <typename C, typename T>
  void
  BasicString<C, T>::Rep::setLeaked() {
    this->referenceCount = -1;
  }

  template <typename C, typename T>
  void
  BasicString<C, T>::Rep::setSharable() {
    this->referenceCount = 0;
  }

  template <typename C, typename T>
  void
  BasicString<C, T>::Rep::setLengthAndSharable(SizeType n) {
    this->setSharable();
    this->length = n;
    TraitsType::assign(this->data()[n], Rep::terminal);
  }

  template <typename C, typename T>
  typename BasicString<C, T>::Pointer
  BasicString<C, T>::Rep::data() {
    return reinterpret_cast<Pointer>(this + 1);
  }

  template <typename C, typename T>
  typename BasicString<C, T>::Pointer
  BasicString<C, T>::Rep::grab() {
    return this->isLeaked() ? this->clone() : this->copy();
  }

  template <typename C, typename T>
  void
  BasicString<C, T>::Rep::dispose() {
    if (this != &Rep::emptyRep())
      if (this->referenceCount-- <= 0)
        this->destroy();
  }

  template <typename C, typename T>
  typename BasicString<C, T>::Pointer
  BasicString<C, T>::Rep::copy() {
    if (this != &Rep::emptyRep())
      this->referenceCount++;
    return this->data();
  }

  template <typename C, typename T>
  typename BasicString<C, T>::Rep*
  BasicString<C, T>::Rep::create(SizeType capacity, SizeType oldCapacity) {
    assertNotGt(capacity, Rep::maximumSize);
    if (capacity > Rep::maximumSize)
      Exception::throwException(LengthException(
          TEXT("BasicString::Rep::create")));

    const SizeType pageSize = System::pageSize();
    const SizeType mallocHeaderSize = 4 * sizeof (void*);

    if (capacity > oldCapacity && capacity < 2 * oldCapacity)
      capacity = 2 * oldCapacity;

    SizeType size = (capacity + 1) * sizeof (ValueType) + sizeof (Rep);
    const SizeType adjSize = size + mallocHeaderSize;
    if (adjSize > pageSize && capacity > oldCapacity) {
      const SizeType extra = pageSize - adjSize % pageSize;
      capacity += extra / sizeof (ValueType);

      if (capacity > Rep::maximumSize)
        capacity = Rep::maximumSize;
      size = (capacity + 1) * sizeof (ValueType) + sizeof (Rep);
    }

    void* place = malloc(size);
    assertNotNull(place);

    if (place == nullptr)
      Exception::throwException(OutOfMemoryException(
          TEXT("BasicString::Rep::create")));

    Rep* rep = new (place) Rep;
    rep->capacity = capacity;
    rep->setSharable();

    return rep;
  }

  template <typename C, typename T>
  typename BasicString<C, T>::Pointer
  BasicString<C, T>::Rep::clone(SizeType res) {
    const SizeType requestedCapacity = this->length + res;
    Rep* rep = Rep::create(requestedCapacity, this->capacity);

    if (this->length != 0)
      BasicString<C, T>::copy(rep->data(), this->data(), this->length);

    rep->setLengthAndSharable(this->length);
    return rep->data();
  }

  template <typename C, typename T>
  void
  BasicString<C, T>::Rep::destroy() {
    free(this);
  }

  template <typename C, typename T>
  typename BasicString<C, T>::Pointer
  BasicString<C, T>::data() const {
    return this->referenceData_;
  }

  template <typename C, typename T>
  typename BasicString<C, T>::Pointer
  BasicString<C, T>::data(Pointer data) {
    assertNotNull(data);
    return this->referenceData_ = data;
  }

  template <typename C, typename T>
  typename BasicString<C, T>::Rep*
  BasicString<C, T>::rep() const {
    return &((reinterpret_cast<Rep*>(this->referenceData_))[-1]);
  }

  template <typename C, typename T>
  typename BasicString<C, T>::Rep&
  BasicString<C, T>::emptyRep() {
    return BasicString::Rep::emptyRep();
  }

  template <typename C, typename T>
  typename BasicString<C, T>::Iterator
  BasicString<C, T>::iBegin() const {
    return Iterator(this->data());
  }

  template <typename C, typename T>
  typename BasicString<C, T>::Iterator
  BasicString<C, T>::iEnd() const {
    return Iterator(this->data() + this->length());
  }

  template <typename C, typename T>
  void
  BasicString<C, T>::leak() {
    if (!this->rep()->isLeaked())
      this->leakHard();
  }

  template <typename C, typename T>
  void
  BasicString<C, T>::leakHard() {
    if (this->rep() == &BasicString::emptyRep())
      return;

    Rep* rep = this->rep();
    if (rep->isShared())
      this->mutate(0, 0, 0);
    rep->setLeaked();
  }

  template <typename C, typename T>
  typename BasicString<C, T>::SizeType
  BasicString<C, T>::check(SizeType pos, const Char* str) const {
    if (pos > this->length())
      Exception::throwException(OutOfRangeException(str));

    return pos;
  }

  template <typename C, typename T>
  void
  BasicString<C, T>::checkLength(SizeType oldLength, SizeType newLength,
      const Char* str) {
    if (this->maximumSize() - (this->length() - oldLength) < newLength)
      Exception::throwException(LengthException(str));
  }

  template <typename C, typename T>
  typename BasicString<C, T>::SizeType
  BasicString<C, T>::limit(SizeType pos, SizeType offset) const {
    return (offset < this->length() - pos) ?
        offset : this->length() - pos;
  }

  template <typename C, typename T>
  Bool
  BasicString<C, T>::disjunct(ConstPointer s) const {
    assertNotNull(s);
    return (s < this->data() ||
        this->data() + this->length() < s);
  }

  template <typename C, typename T>
  void
  BasicString<C, T>::copy(Pointer destination, ConstPointer source,
      SizeType length) {
    assertStringLength(source, length);
    assertNotNull(destination);

    if (length == 1)
      TraitsType::assign(*destination, *source);
    else
      TraitsType::copy(destination, source, length);
  }

  template <typename C, typename T>
  void
  BasicString<C, T>::move(Pointer destination, ConstPointer source,
      SizeType length) {
    assertStringLength(source, length);
    assertNotNull(destination);

    if (length == 1)
      TraitsType::assign(*destination, *source);
    else
      TraitsType::move(destination, source, length);
  }

  template <typename C, typename T>
  void
  BasicString<C, T>::assign(Pointer destination, SizeType length,
      ValueType c) {
    assertStringLength(destination, length);

    if (length == 1)
      TraitsType::assign(*destination, c);
    else
      TraitsType::assign(destination, length, c);
  }

  template <typename C, typename T>
  Int
  BasicString<C, T>::compare(SizeType n1, SizeType n2) {
    const DifferenceType d = DifferenceType(n1 - n2);
    if (d > NumericLimits<Int>::maximum())
      return NumericLimits<Int>::maximum();
    else if (d < NumericLimits<Int>::minimum())
      return NumericLimits<Int>::minimum();
    else
      return Int(d);
  }

  template <typename C, typename T>
  template <typename I>
  void
  BasicString<C, T>::copyChars(Pointer destination, I k1, I k2) {
    assertNotNull(destination);

    for (; k1 <= k2; ++k1, ++destination)
      TraitsType::assign(*destination, *k1);
  }

  template <typename C, typename T>
  void
  BasicString<C, T>::copyChars(Pointer destination, Iterator k1, Iterator k2) {
    assertNotNull(destination);
    BasicString::copyChars(destination, k1.base(), k2.base());
  }

  template <typename C, typename T>
  void
  BasicString<C, T>::copyChars(Pointer destination, ConstIterator k1,
      ConstIterator k2) {
    assertNotNull(destination);
    BasicString::copyChars(destination, k1.base(), k2.base());
  }

  template <typename C, typename T>
  void
  BasicString<C, T>::copyChars(Pointer destination, Pointer k1, Pointer k2) {
    assertNotNull(destination);
    assertNotNull(k1);
    assertNotNull(k2);

    BasicString::copy(destination, k1, k2 - k1);
  }

  template <typename C, typename T>
  void
  BasicString<C, T>::copyChars(Pointer destination, ConstPointer k1,
      ConstPointer k2) {
    assertNotNull(destination);
    assertNotNull(k1);
    assertNotNull(k2);

    BasicString::copy(destination, k1, k2 - k1);
  }

  template <typename C, typename T>
  typename BasicString<C, T>::Pointer
  BasicString<C, T>::construct(SizeType length, ValueType c) {
    if (length == 0)
      return BasicString::emptyRep().data();

    Rep* rep = Rep::create(length, SizeType(0));
    BasicString::assign(rep->data(), length, c);
    rep->setLengthAndSharable(length);

    return rep->data();
  }

  template <typename C, typename T>
  template <typename I>
  typename BasicString<C, T>::Pointer
  BasicString<C, T>::construct(I begin, I end, InputIteratorTag) {
    if (begin == end)
      return BasicString::emptyRep().data();

    Pointer buffer = new ValueType [System::standardBufferSize()];
    assertNotNull(buffer);
    if (buffer == nullptr)
      Exception::throwException(OutOfMemoryException(
          TEXT("BasicString::construct")));

    SizeType length = 0;
    while (begin != end && length < sizeof (buffer) / sizeof(ValueType)) {
      buffer[length++] = *begin;
      ++begin;
    }
    Rep* rep = Rep::create(length, SizeType(0));
    BasicString::copy(rep->data(), buffer, length);

    try {
      while (begin != end) {
        if (length == rep->capacity) {
          Rep* anotherRep = Rep::create(length + 1, SizeType(0));
          rep->destroy();
          rep = anotherRep;
        }
        rep->data()[length++] = *begin;
        ++begin;
      }
    } catch (...) {
      delete [] buffer;
      rep->destroy();
#ifdef LC_EXCEPTIONS
      throw;
#endif /* LC_EXCEPTIONS */
    }

    delete [] buffer;
    rep->setLengthAndSharable(length);
    return rep->data();
  }

  template <typename C, typename T>
  template <typename I>
  typename BasicString<C, T>::Pointer
  BasicString<C, T>::construct(I begin, I end, ForwardIteratorTag) {
    if (begin == end)
      return BasicString::emptyRep().data();

    if (isNull(begin) || isNull(end))
      Exception::throwException(NullPointerException(
          TEXT("BasicString::construct_")));

    SizeType length = implicit_cast<SizeType>(distance(begin, end));
    Rep* rep = Rep::create(length, SizeType(0));

    try {
      BasicString::copyChars(rep->data(), begin, end);
    } catch (...) {
      rep->destroy();
#ifdef LC_EXCEPTIONS
      throw;
#endif /* LC_EXCEPTIONS */
    }

    rep->setLengthAndSharable(length);
    return rep->data();
  }

  template <typename C, typename T>
  void
  BasicString<C, T>::mutate(SizeType pos, SizeType length1, SizeType length2) {
    const SizeType oldLength = this->length();
    const SizeType newLength = oldLength + length2 - length1;
    const SizeType howMuch = oldLength - pos - length1;

    if (oldLength - pos < length1)
      Exception::throwException(LengthException(TEXT("BasicString::mutate")));

    if (newLength > this->capacity() || this->rep()->isShared()) {
      Rep* rep = Rep::create(newLength, this->capacity());
      if (pos)
        BasicString::copy(rep->data(), this->data(), pos);
      if (howMuch)
        BasicString::copy(rep->data() + pos + length2, this->data() + pos +
            length1, howMuch);
      this->rep()->dispose();
      this->data(rep->data());
    } else if (howMuch && length1 != length2) {
      BasicString::move(this->data() + pos + length2, this->data() + pos +
          length1, howMuch);
    }

    this->rep()->setLengthAndSharable(newLength);
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::replaceSafe(SizeType pos, SizeType length1,
      ConstPointer str, SizeType length2) {
    assertStringLength(str, length2);
    this->mutate(pos, length1, length2);

    if (length2)
      BasicString::copy(this->data() + pos, str, length2);

    return *this;
  }

  template <typename C, typename T>
  void
  BasicString<C, T>::sprintfHelper(Pointer buffer, SSize& length,
      ConstPointer format, va_list args) {
    assertNotNull(buffer);
    assertNotNull(format);

    va_list argsCopy;
    va_copy(argsCopy, args);

    SizeType allocLength = length;

    while (true) {
      length = TraitsType::vsnprintf(buffer, allocLength, format, args);

      if (length == SSize(allocLength)) {
        allocLength *= 2;

        delete [] buffer;
        buffer = new ValueType [allocLength];
        assertNotNull(buffer);
        if (isNull(buffer))
          Exception::throwException(OutOfMemoryException(
              TEXT("BasicString::sprintfHelper")));

        va_copy(args, argsCopy);
      } else {
        break;
      }
    }
    va_end(argsCopy);
  }

  template <typename C, typename T>
  BasicString<C, T>::BasicString() {
    this->referenceData_ = BasicString::construct(SizeType(), Rep::terminal);
  }

  template <typename C, typename T>
  BasicString<C, T>::BasicString(const BasicString& str) {
    this->referenceData_ = str.rep()->grab();
  }

  template <typename C, typename T>
  BasicString<C, T>::BasicString(const BasicString& str, const SizeType pos,
      const SizeType length) {
    BasicString(str.data() +
        str.check(pos, TEXT("BasicString::BasicString")),
        str.limit(pos, length));
  }

  template <typename C, typename T>
  BasicString<C, T>::BasicString(SizeType length, ValueType c) {
    this->referenceData_ = BasicString::construct(length, c);
  }

  template <typename C, typename T>
  BasicString<C, T>::BasicString(ConstPointer str, SizeType length) {
    this->referenceData_ = BasicString::construct(str, str + length,
        typename IteratorTraits<ConstPointer>::IteratorCategory());
  }

  template <typename C, typename T>
  BasicString<C, T>::BasicString(ConstPointer str) {
    SizeType length = implicit_cast<SizeType>(TraitsType::length(str));
    this->referenceData_ = BasicString::construct(str, str + length,
        typename IteratorTraits<ConstPointer>::IteratorCategory());
  }

  template <typename C, typename T>
  BasicString<C, T>::~BasicString() {
    this->rep()->dispose();
  }

  template <typename C, typename T>
  typename BasicString<C, T>::SizeType
  BasicString<C, T>::length() const {
    return this->rep()->length;
  }

  template <typename C, typename T>
  typename BasicString<C, T>::SizeType
  BasicString<C, T>::size() const {
    return this->rep()->length;
  }

  template <typename C, typename T>
  typename BasicString<C, T>::SizeType
  BasicString<C, T>::maximumSize() const {
    return Rep::maximumSize;
  }

  template <typename C, typename T>
  typename BasicString<C, T>::SizeType
  BasicString<C, T>::capacity() const {
    return this->rep()->capacity;
  }

  template <typename C, typename T>
  Bool
  BasicString<C, T>::isEmpty() const {
    return this->size() == 0;
  }

  template <typename C, typename T>
  typename BasicString<C, T>::ConstPointer
  BasicString<C, T>::toCString() const {
    return this->data();
  }

  template <typename C, typename T>
  typename BasicString<C, T>::Iterator
  BasicString<C, T>::begin() {
    this->leak();
    return Iterator(this->data());
  }

  template <typename C, typename T>
  typename BasicString<C, T>::ConstIterator
  BasicString<C, T>::begin() const {
    return ConstIterator(this->data());
  }

  template <typename C, typename T>
  typename BasicString<C, T>::Iterator
  BasicString<C, T>::end() {
    this->leak();
    return Iterator(this->data() + this->size());
  }

  template <typename C, typename T>
  typename BasicString<C, T>::ConstIterator
  BasicString<C, T>::end() const {
    return ConstIterator(this->data() + this->size());
  }

  template <typename C, typename T>
  void
  BasicString<C, T>::clear() {
    this->mutate(0, this->size(), 0);
  }

  template <typename C, typename T>
  typename BasicString<C, T>::Reference
  BasicString<C, T>::front() {
    return *this->begin();
  }

  template <typename C, typename T>
  typename BasicString<C, T>::ConstReference
  BasicString<C, T>::front() const {
    return *this->begin();
  }

  template <typename C, typename T>
  typename BasicString<C, T>::Reference
  BasicString<C, T>::back() {
    return *(--this->end());
  }

  template <typename C, typename T>
  typename BasicString<C, T>::ConstReference
  BasicString<C, T>::back() const {
    return *(--this->end());
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::pushFront(ValueType c) {
    return this->prepend(c, SizeType(1));
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::pushBack(ValueType c) {
    return this->append(c, SizeType(1));
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::popFront() {
    this->mutate(0, SizeType(1), 0);
    return *this;
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::popBack() {
    this->mutate(this->size() - 1, SizeType(1), 0);
    return *this;
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::assign(const BasicString& str) {
    if (this->rep() != str.rep()) {
      Pointer data = str.rep()->grab();
      this->rep()->dispose();
      this->data(data);
    }
    return *this;
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::assign(ConstPointer str, SizeType length) {
    assertStringLength(str, length);
    if (isNull(str))
      Exception::throwException(NullPointerException(
          TEXT("BasicString::assign")));

    this->checkLength(this->length(), length, TEXT("BasicString::assign"));

    if (this->disjunct(str) || this->rep()->isShared()) {
      this->replaceSafe(0, this->length(), str, length);
    } else {
      const SizeType pos = str - this->data();
      if (pos >= length) {
        BasicString::copy(this->data(), str, length);
      } else if (pos != 0) {
        BasicString::move(this->data(), str, length);
      }
      this->data()[length] = Rep::terminal;
      this->rep()->setLengthAndSharable(length);
    }

    return *this;
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::assign(const BasicString& str, SizeType pos,
      SizeType length) {
    return this->assign(str.data() +
        str.check(pos, TEXT("BasicString::assign")), str.limit(pos, length));
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::assign(ConstPointer str) {
    return this->assign(str, TraitsType::length(str));
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::assign(ValueType c, SizeType n) {
    this->checkLength(this->length(), n, TEXT("BasicString::assign"));
    if (this->rep()->isShared()) {
      this->mutate(0, this->length(), n);
    } else {
      this->reserve(n);
    }

    if (n > 0)
      TraitsType::assign(this->data(), n, c);
    this->rep()->setLengthAndSharable(n);
    this->data()[n] = Rep::terminal;

    return *this;
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::prepend(const BasicString<C, T>& str) {
      return this->prepend(str.data(), str.length());
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::prepend(const BasicString& str, SizeType pos,
      SizeType length) {
    return this->prepend(str.data() +
        str.check(pos, TEXT("BasicString::prepend")), str.limit(pos, length));
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::prepend(ConstPointer str, SizeType length) {
    assertStringLength(str, length);
    if (isNull(str))
      Exception::throwException(NullPointerException(
            TEXT("BasicString::assign")));

    if (length != 0) {
      this->checkLength(0, length, TEXT("BasicString::prepend"));
      const SizeType newLength = this->length() + length;

      if (newLength > this->capacity() || this->rep()->isShared()) {
        if (this->disjunct(str)) {
          this->reserve(newLength);
        } else {
          const SizeType offset = str - this->data();
          this->reserve(newLength);
          str = this->data() + offset;
        }
      }
      BasicString::move(this->data() + length, this->data(), this->length());
      BasicString::copy(this->data(), str, length);
      this->rep()->setLengthAndSharable(newLength);
      this->data()[newLength] = Rep::terminal;
    }
    return *this;
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::prepend(ConstPointer str) {
    return this->prepend(str, TraitsType::length(str));
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::prepend(ValueType c, SizeType n) {
    if (n > 0) {
      this->checkLength(0, n, TEXT("BasicString::prepend"));
      const SizeType newLength = this->length() + n;

      if (newLength > this->capacity() || this->rep()->isShared())
        this->reserve(newLength);
      BasicString::move(this->data() + n, this->data(), this->length());
      TraitsType::assign(this->data(), n, c);
      this->rep()->setLengthAndSharable(newLength);
      this->data()[newLength] = Rep::terminal;
    }
    return *this;
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::append(const BasicString& str) {
    const SizeType length = str.length();
    if (length != 0) {
      const SizeType newLength = length + this->length();
      if (newLength > this->capacity() || this->rep()->isShared())
        this->reserve(newLength);
      BasicString::copy(this->data() + this->length(), str.data(), length);
      this->rep()->setLengthAndSharable(newLength);
      this->data()[newLength] = Rep::terminal;
    }

    return *this;
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::append(const BasicString& str, SizeType pos,
      SizeType length) {
    return this->append(str.data() +
        str.check(pos, TEXT("BasicString::append")), str.limit(pos, length));
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::append(ConstPointer str, SizeType length) {
    assertStringLength(str, length);
    if (isNull(str))
      Exception::throwException(NullPointerException(
          TEXT("BasicString::append")));

    if (length != 0) {
      this->checkLength(0, length, TEXT("BasicString::append"));
      const SizeType newLength = length + this->length();

      if (newLength > this->capacity() || this->rep()->isShared()) {
        if (this->disjunct(str)) {
          this->reserve(newLength);
        } else {
          const SizeType offset = str - this->data();
          this->reserve(newLength);
          str = this->data() + offset;
        }
      }
      BasicString::copy(this->data() + this->length(), str, length);
      this->rep()->setLengthAndSharable(newLength);
      this->data()[newLength] = Rep::terminal;
    }
    return *this;
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::append(ConstPointer str) {
    return this->append(str, TraitsType::length(str));
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::append(ValueType c, SizeType n) {
    if (n > 0) {
      this->checkLength(0, n, TEXT("BasicString::append"));
      const SizeType newLength = n + this->length();

      if (newLength > this->capacity() || this->rep()->isShared())
        this->reserve(newLength);
      TraitsType::assign(this->data() + this->length(), n, c);
      this->rep()->setLengthAndSharable(newLength);
      this->data()[newLength] = Rep::terminal;
    }
    return *this;
  }

  template <typename C, typename T>
  void
  BasicString<C, T>::reserve(SizeType res) {
    if (res != this->capacity() || this->rep()->isShared()) {
      if (res < this->length())
        res = this->length();
      Pointer data = this->rep()->clone(res - this->length());
      this->rep()->dispose();
      this->data(data);
    }
  }

  template <typename C, typename T>
  Int
  BasicString<C, T>::compare(const BasicString& str) const {
    const SizeType length = this->length();
    const SizeType otherLength = str.length();
    const SizeType compareLength = cyan::minimum(length, otherLength);

    Int returnValue = TraitsType::compare(this->data(), str.data(),
        compareLength);
    if (returnValue == 0)
      returnValue = BasicString::compare(length, otherLength);
    return returnValue;
  }

  template <typename C, typename T>
  Int
  BasicString<C, T>::compare(ConstPointer str) const {
    assertNotNull(str);
    if (isNull(str))
      Exception::throwException(NullPointerException(
            TEXT("BasicString::compare")));

    const SizeType length = this->length();
    const SizeType otherLength = TraitsType::length(str);
    const SizeType compareLength = cyan::minimum(length, otherLength);

    Int returnValue = TraitsType::compare(this->data(), str, compareLength);
    if (returnValue == 0)
      returnValue = BasicString::compare(length, otherLength);
    return returnValue;
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::formattedAssign(ConstPointer format, ...) {
    assertNotNull(format);
    if (isNull(format))
      Exception::throwException(NullPointerException(
          TEXT("BasicString::sprintf")));

    SSize length = System::standardBufferSize();
    Pointer buffer = new ValueType [length];
    va_list args;

    try {
      va_start(args, format);
      BasicString::sprintfHelper(buffer, length, format, args);
      va_end(args);
    } catch (...) {
      va_end(args);
      delete [] buffer;
#ifdef LC_EXCEPTIONS
      throw;
#endif /* LC_EXCEPTIONS */
    }

    if (length < 0) {
      delete [] buffer;
      Exception::throwException(RuntimeException(
          TEXT("BasicString::sprintf")));
    } else {
      this->assign(buffer, length);
      delete [] buffer;
    }

    return *this;
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::formattedPrepend(ConstPointer format, ...) {
    assertNotNull(format);
    if (isNull(format))
      Exception::throwException(NullPointerException(
          TEXT("BasicString::sprintf")));

    SSize length = System::standardBufferSize();
    Pointer buffer = new ValueType [length];
    va_list args;

    try {
      va_start(args, format);
      BasicString::sprintfHelper(buffer, length, format, args);
      va_end(args);
    } catch (...) {
      va_end(args);
      delete [] buffer;
#ifdef LC_EXCEPTIONS
      throw;
#endif /* LC_EXCEPTIONS */
    }

    if (length < 0) {
      delete [] buffer;
      Exception::throwException(RuntimeException(
          TEXT("BasicString::sprintf")));
    } else {
      this->prepend(buffer, length);
      delete [] buffer;
    }

    return *this;
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::formattedAppend(ConstPointer format, ...) {
    assertNotNull(format);
    if (isNull(format))
      Exception::throwException(NullPointerException(
          TEXT("BasicString::sprintf")));

    SSize length = System::standardBufferSize();
    Pointer buffer = new ValueType [length];
    va_list args;

    try {
      va_start(args, format);
      BasicString::sprintfHelper(buffer, length, format, args);
      va_end(args);
    } catch (...) {
      va_end(args);
      delete [] buffer;
#ifdef LC_EXCEPTIONS
      throw;
#endif /* LC_EXCEPTIONS */
    }

    if (length < 0) {
      delete [] buffer;
      Exception::throwException(RuntimeException(
        TEXT("BasicString::sprintf")));
    } else {
      this->append(buffer, length);
      delete [] buffer;
    }

    return *this;
  }

  template <typename C, typename T>
  Int32
  BasicString<C, T>::toInt32() const {
    Int32 returnValue = 0;
    if (TraitsType::parseInt32(this->data(), returnValue))
      return returnValue;
    else
      return NumericLimits<Int32>::minimum();
  }

  template <typename C, typename T>
  Int64
  BasicString<C, T>::toInt64() const {
    Int64 returnValue = 0;
    if (TraitsType::parseInt64(this->data(), returnValue))
      return returnValue;
    else
      return NumericLimits<Int64>::minimum();
  }

  template <typename C, typename T>
  Double
  BasicString<C, T>::toDouble() const {
    Double returnValue = 0;
    if (TraitsType::parseDouble(this->data(), returnValue))
      return returnValue;
    else
      return -1.00;
  }

  template <typename C, typename T>
  typename BasicString<C, T>::SizeType
  BasicString<C, T>::find(ConstPointer str, SizeType pos,
      SizeType lengthToSearch) const {
    assertStringLength(str, lengthToSearch);
    if (isNull(str))
      Exception::throwException(NullPointerException(
          TEXT("BasicString::find")));

    const SizeType length = this->length();
    ConstPointer data = this->data();

    if (lengthToSearch == 0)
      return pos <= length ? pos : BasicString::npos;

    if (lengthToSearch <= length) {
      for (; pos + lengthToSearch <= length; ++pos)
        if (TraitsType::eq(data[pos], str[0]) && TraitsType::compare(data +
              pos + 1, str + 1, lengthToSearch - 1) == 0)
          return pos;
    }
    return BasicString::npos;
  }

  template <typename C, typename T>
  typename BasicString<C, T>::SizeType
  BasicString<C, T>::find(const BasicString& str, SizeType pos) const {
    return this->find(str.data(), pos, str.length());
  }

  template <typename C, typename T>
  typename BasicString<C, T>::SizeType
  BasicString<C, T>::find(ConstPointer str, SizeType pos) const {
    return this->find(str, pos, TraitsType::length(str));
  }

  template <typename C, typename T>
  typename BasicString<C, T>::SizeType
  BasicString<C, T>::find(ValueType c, SizeType pos) const {
    SizeType returnValue = BasicString::npos;
    const SizeType length = this->length();

    if (pos < length) {
      ConstPointer data = this->data();
      const SizeType lengthToSearch = length - pos;
      ConstPointer p = TraitsType::find(data + pos, lengthToSearch, c);
      if (p)
        returnValue = p - data;
    }
    return returnValue;
  }

  template <typename C, typename T>
  BasicString<C, T>
  BasicString<C, T>::substring(SizeType pos, SizeType length) const {
    return BasicString(*this, this->check(pos,
        TEXT("BasicString::substring")), length);
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::findAndReplace(SizeType pos, ConstPointer searchStr,
      ConstPointer replaceStr) {
    assertNotNull(searchStr);
    assertNotNull(replaceStr);
    if (isNull(searchStr) || isNull(replaceStr))
      Exception::throwException(NullPointerException(
          TEXT("BasicString::findAndReplace")));

    const SizeType searchStrLength = TraitsType::length(searchStr);

    if (searchStrLength != 0) {
      const SizeType replaceStrLength = TraitsType::length(replaceStr);

      while (pos + searchStrLength <= this->length()) {
        pos = this->find(searchStr, pos, searchStrLength);

        if (pos <= this->length())
          this->replaceSafe(pos, searchStrLength, replaceStr,
              replaceStrLength);
        else
          break;

        pos += replaceStrLength;
      }
    }

    return *this;
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::findAndReplace(ConstPointer searchStr,
      ConstPointer replaceStr) {
    return this->findAndReplace(0, searchStr, replaceStr);
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::stripLChar(ValueType c) {
    ConstIterator it;
    for (it = this->iBegin(); it != this->iEnd(); ++it) {
      if (!TraitsType::eq(*it, c))
        break;
    }

    const SizeType lengthToMutate = distance(this->iBegin(), it);

    if (lengthToMutate > 0)
      this->mutate(0, lengthToMutate, 0);

    return *this;
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::stripRChar(ValueType c) {
    ConstIterator it;
    for (it = this->iEnd(), --it; it != this->iBegin(); --it) {
      if (!TraitsType::eq(*it, c))
        break;
    }

    const SizeType lengthToMutate = distance(it, this->iEnd());
    const SizeType pos = this->length() - lengthToMutate;

    if (lengthToMutate > 0)
      this->mutate(pos + 1, lengthToMutate - 1, 0);

    return *this;
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::stripWhiteSpace() {
    ConstIterator it;
    for (it = this->iBegin(); it != this->iEnd(); ++it) {
      if (!TraitsType::isWhiteSpace(*it))
        break;
    }

    SizeType lengthToMutate = distance(this->iBegin(), it);

    if (lengthToMutate > 0)
      this->mutate(0, lengthToMutate, 0);

    for (it = this->iEnd(), --it; it != this->iBegin(); --it) {
      if (!TraitsType::isWhiteSpace(*it))
        break;
    }

    lengthToMutate = distance(it, this->iEnd());
    const SizeType pos = this->length() - lengthToMutate;

    if (lengthToMutate > 0)
      this->mutate(pos + 1, lengthToMutate - 1, 0);

    return *this;
  }

  template <typename C, typename T>
  String
  BasicString<C, T>::toString() const {
    const SizeType mySize = this->size();
    ScopedArray<Char> mbstr(new Char [mySize]);

    const SizeType newSize = TraitsType::toMbs(mbstr, this->toCString(),
        mySize);

    assertNotEqual(newSize, NumericLimits<SizeType>::maximum());
    if (newSize != NumericLimits<SizeType>::maximum())
      return String(mbstr, newSize);
    return String();
  }

  template <typename C, typename T>
  WString
  BasicString<C, T>::toWString() const {
    const SizeType mySize = this->size();
    ScopedArray<WChar> wcstr(new WChar [mySize]);

    const SizeType newSize = TraitsType::toWcs(wcstr, this->toCString(),
        mySize);

    assertNotEqual(newSize, NumericLimits<SizeType>::maximum());
    if (newSize != NumericLimits<SizeType>::maximum())
      return WString(wcstr, newSize);
    return WString();
  }

  template <typename C, typename T>
  UInt32
  BasicString<C, T>::hashCode() const {
    UInt32 hash = Object::hashSeed;
    for (ConstIterator i = this->begin(); i != this->end(); ++i) {
      typename TraitsType::IntType c = TraitsType::toIntType(*i);
      hash = ((hash << 5) + hash) ^ c;
    }
    return hash;
  }

  template <typename C, typename T>
  Bool
  BasicString<C, T>::operator ==(const BasicString& str) const {
    return this->compare(str) == 0;
  }

  template <typename C, typename T>
  Bool
  BasicString<C, T>::operator ==(ConstPointer str) const {
    return this->compare(str) == 0;
  }

  template <typename C, typename T>
  Bool
  BasicString<C, T>::operator !=(const BasicString& str) const {
    return this->compare(str) != 0;
  }

  template <typename C, typename T>
  Bool
  BasicString<C, T>::operator !=(ConstPointer str) const {
    return this->compare(str) != 0;
  }

  template <typename C, typename T>
  typename BasicString<C, T>::ConstReference
  BasicString<C, T>::operator [](SizeType pos) const {
    assertLtOrEq(pos, this->size());
    return this->data()[this->check(pos, TEXT("BasicString::operator []"))];
  }

  template <typename C, typename T>
  typename BasicString<C, T>::Reference
  BasicString<C, T>::operator [](SizeType pos) {
    assertLtOrEq(pos, this->size());
    this->leak();
    return this->data()[this->check(pos, TEXT("BasicString::operator []"))];
  }

  template <typename C, typename T>
  BasicString<C, T>::operator ConstPointer() const {
    return const_cast<ConstPointer> (this->data());
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::operator =(const BasicString& value) {
    this->assign(value);
    return *this;
  }

  template <typename C, typename T>
  BasicString<C, T>&
  BasicString<C, T>::operator =(ConstPointer value) {
    this->assign(value);
    return *this;
  }

  template <typename C, typename T>
  Bool
  operator ==(typename BasicString<C, T>::ConstPointer cstr,
    const BasicString<C, T>& str) {
    return str.compare(cstr) == 0;
  }

  template <typename C, typename T>
  Bool
  operator !=(typename BasicString<C, T>::ConstPointer cstr,
      const BasicString<C, T>& str) {
    return str.compare(cstr) != 0;
  }

  template class BasicString<Char>;
  template class BasicString<WChar>;
}
